package com.atwy.tree;

/**
 * 线索化二叉树
 * 在二叉树的结点上加上线索的二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，
 * 使其变为线索二叉树的过程称为对二叉树进行线索化。
 * <p>
 * 对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，
 * 利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，
 * 这些指针称为线索，加上线索的二叉树称为线索二叉树。
 * <p>
 * 对于一个有n个节点的二叉链表，每个节点有指向左右节点的2个指针域，整个二叉链表存在2n个指针域。
 * 而n个节点的二叉链表有n-1条分支线，那么空指针域的个数=2n-(n-1) = n+1个空指针域.
 * 利用二叉链表中的空指针域，存放节点在某种遍历方式下的前驱和后继节点的指针
 * <p>
 * 线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题，
 * 解决了二叉链表找左、右孩子困难的问题。
 * <p>
 * 二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构，
 * 使每个结点都有了唯一前驱和后继（第一个结点无前驱，最后一个结点无后继）。
 * 对于二叉树的一个结点，查找其左右子女是方便的，其前驱后继只有在遍历中得到。
 * 为了容易找到前驱和后继，有两种方法。
 * 一是在结点结构中增加向前和向后的指针，这种方法增加了存储开销，不可取；
 * 二是利用二叉树的空链指针。
 * <p>
 * 参考资料：https://blog.csdn.net/jisuanjiguoba/article/details/81092812
 */
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {

        TreeNode node = new TreeNode(1, "宋江");
        TreeNode node2 = new TreeNode(2, "卢俊义");
        TreeNode node3 = new TreeNode(3, "吴用");
        TreeNode node4 = new TreeNode(4, "公孙胜");
        TreeNode node5 = new TreeNode(5, "关胜");
        TreeNode node6 = new TreeNode(6, "林冲");

        node.setLeft(node2);
        node.setRight(node3);

        node2.setLeft(node4);
        node2.setRight(node5);

        node3.setLeft(node6);

        // 将上述构建的二叉树线索化
        ThreadedBinaryTree binaryTree = new ThreadedBinaryTree(node);
        binaryTree.setRoot(node);
        binaryTree.threadedNodes();

        System.out.println("中序线索化后的中序遍历结果：");
        binaryTree.threadedList();

        // 测试线索化后结点的前序和后继
        TreeNode left = node5.getLeft();
        TreeNode right = node5.getRight();
        System.out.println("========");
        System.out.println("结点5的前驱结点：" + left);
        System.out.println("结点5的后继结点：" + right);


    }
}

/**
 * 具有线索化功能的二叉树
 */
class ThreadedBinaryTree {
    private TreeNode root;

    private TreeNode preNode;// 线索化时记录前一个结点

    public ThreadedBinaryTree(TreeNode root) {
        this.root = root;
    }

    public void threadedNodes() {
        this.threadedNodes(root);
    }

    /**
     * 中序线索化二叉树
     *
     * @param node 当前需要线索化的结点
     */
    private void threadedNodes(TreeNode node) {
        if (node == null) {// 为空不能线索化
            return;
        }
        // 先线索化左子树
        threadedNodes(node.getLeft());

        // 处理当前结点的前驱结点
        if (node.getLeft() == null) {
            // 当前结点没有左子树，那就让左指针指向前驱结点
            node.setLeft(preNode);
            // 修改左指针的类型
            node.setLeftThread(true);
        }
        // 处理后继结点
        // 后继结点是前一个结点指向下一个结点，当前结点是不知道谁指向自己的，唯一知道的是有个结点的后继结点指向了自己
        // 需要判断上一个结点的右指针指向null，才能构建后继结点
        if (preNode != null && preNode.getRight() == null) {
            // 上一个结点的后继结点是当前结点
            preNode.setRight(node);
            preNode.setRightThread(true);
        }
        // 在线索化右子树时，前一个结点变成了当前结点，也就是当前结点就是右子树的前一个结点
        preNode = node;

        // 线索化右子树
        threadedNodes(node.getRight());

    }

    /**
     * 遍历 中序线索化二叉树，中序遍历
     */
    public void threadedList() {
        TreeNode node = root;
        // 先找到最左子节点开始
        while (node != null) {
            while (!node.isLeftThread()) {// 非线索化，继续找
                node = node.getLeft();
            }
            // 打印当前结点
            System.out.println(node);

            // 如果当前结点有后继结点，一直输出
            while (node.isRightThread()) {
                node = node.getRight();
                System.out.println(node);
            }
            // 右子树
            node = node.getRight();

        }
    }

    public TreeNode getRoot() {
        return root;
    }

    public void setRoot(TreeNode root) {
        this.root = root;
    }
}

class TreeNode {
    private int id;
    private String name;

    private TreeNode left;
    private TreeNode right;

    private boolean isLeftThread = false;// false表示指向的是左子树, true表示指向前驱结点
    private boolean isRightThread = false;// false表示指向的是右子树, true则表示指向后继结点

    public TreeNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }

    public boolean isLeftThread() {
        return isLeftThread;
    }

    public void setLeftThread(boolean leftThread) {
        isLeftThread = leftThread;
    }

    public boolean isRightThread() {
        return isRightThread;
    }

    public void setRightThread(boolean rightThread) {
        isRightThread = rightThread;
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("TreeNode{");
        sb.append("id=").append(id);
        sb.append(", name='").append(name).append('\'');
        sb.append('}');
        return sb.toString();
    }
}
